package cn.edu.neu.softlab.jason.offer.jianzhioffer.datastructure;

/**
 * 剑指offer-面试10
 * 二进制中1的个数
 * 请实现一个函数，输入一个整数，输出改数二进制中1的个数。例如9表示成二进制是1001，有2个1。
 * 因此输入9，函数输出为2。
 *
 * 一个整数减1之后再和原来的整数做按位与，得到的结果相当于把整数的二进制中最右的一个1变成0。
 */

public class Mianshi10 {
    public static void main(String[] args) {
        //Integer.bitCount()函数能够直接得到
        System.out.println(Integer.bitCount(-1));
        /**
         * java << >> 不是循环左移和循环右移
         * 在移位运算中，如果被移位的操作数是int类型的，那么只会用到移位数的最低5位，如果是long类型的，那么只会用到低六位。
         * 那么为什么是低5位和低6位呢？相信你应该明白了，int共占32位，long占64位，正好是2的5次幂和6次幂。可以理解为分别对
         * 32 和 64 取模。所以1L << 64 就会变成 1L << 0，结果自然就是1了。
         */
        System.out.println(1 << 31);
        System.out.println(-2147483648 << 31);
        System.out.println(1 << 32);
        System.out.println(3 << 30);
        System.out.println(3 << 31);
        System.out.println(3 << 32);
        System.out.println(Integer.toBinaryString(-1));
        System.out.println(Integer.toBinaryString(-1 >> 1));
        System.out.println(Integer.toBinaryString(-1 << 1));
        System.out.println(getCountof1Optimal(1));
        System.out.println(getCountof1Optimal(9));
        System.out.println(getCountof1Optimal(-1));
        System.out.println(getCountof1subOptimal(1));
        System.out.println(getCountof1subOptimal(9));
        System.out.println(getCountof1subOptimal(-1));
        System.out.println(getCountOf1(-1));
    }

    /**
     * 该方法只适用于正整数,具体原因见主程序
     *
     * @param num
     * @return
     */
    public static int getCountOf1(int num) {
        int count = 0;
        while (num != 0) {
            if ((num & 1) != 0) {
                count++;
            }
            // >>> 为无符号右移，此时可以用于正负数
            //num = num >>> 1;
            num = num >> 1;
        }
        return count;
    }

    public static int getCountof1subOptimal(int num) {
        int count = 0;
        int flag = 1;
        while (flag != 0) {
            if ((flag & num) != 0) {
                count++;
            }
            flag = flag << 1;
        }
        return count;
    }

    public static int getCountof1Optimal(int num) {
        int count = 0;
        while (num != 0) {
            count++;
            num = num & (num - 1);
        }
        return count;
    }
}
